Detección centralizada de deadlock
Características.
El nodo de control puede mantener el grafo global constantemente o lo puede construir en un momento dado.
Es conceptualmente simple y fácil de implementar.
La resolución del deadlock es optima ya que el nodo de control tiene toda la información y puede tomar la decisión más acertada.
11
Detección centralizada de deadlock
Desventajas.
Embotellamiento generado alrededor del nodo de control o coordinados.
Punto único de falla.
12
Detección distribuida de deadlock
La responsabilidad de detectar el deadlock es compartida equitativamente entre todos los nodos.
Estudiaremos el algoritmo de:
Chandy-Misra-Hass (1983).
13
Chandy-Misra-Hass
Se utiliza cuando un proceso debe esperar por cierto recurso.
Se utiliza un mensaje especial.
Mensaje de exploración.
El mensaje consta de:
El proceso recién bloqueado.
El proceso que envía el mensaje.
El proceso a cual se envía.
14
Chandy-Misra-Hass
15
Algoritmo Chandy-Misra-Hass
Todos los procesos poseen en su memoria local las siguientes estructuras para poder llevar a cabo el algoritmo propuesto:
ultimo(i): en este arreglo se almacena el número de secuencia más grande en cualquier consulta enviada o recibida por Pk (el valor de m más grande).
IDUltimo(i): almacena el Id del proceso que envió el mensaje más reciente, y cuyo valor m se almacenó en Ultimo(i).
num(i): almacena la cantidad de mensajes consulta(i,m,k,j) que envió Pk y aún no han sido respondidos con su correspondiente mensaje respuesta(i,m,j,k). Si num(i) es 0, significa que Pk ha recibido respuesta de cada una de las consultas enviadas.
espera(i): es verdadero si Pk está ocioso. Se hace falso cuando Pk pasa a estado En Ejecución.
Cada proceso p almacena localmente su conjunto dependiente en el arreglo dependientes(p).
16
Algoritmo Chandy-Misra-Hass
17
Algoritmo Chandy-Misra-Hass
18
Algoritmo Chandy-Misra-Hass
19
Algoritmo Chandy-Misra-Hass
Asignación.
Realizar la corrida del algoritmo de Chandy-Misra-Hass, con el estado inicial de la figura.
20
(Gp:) P1
(Gp:) P4
(Gp:) P3
(Gp:) P2
(Gp:) Nodo 1
(Gp:) Nodo 2
Chandy-Misra-Hass
Características.
Cada nodo mantiene una porción del grafo global.
Cada nodo participa en la detección de un ciclo global.
Son más resistentes a fallas, y ningún nodo está sobrecargado con la detección de deadlock.
21
Chandy-Misra-Hass
Desventajas.
Debido a las estructuras de datos su diseño resulta muy complejo.
22
Detección jerárquica de deadlock
Los nodos se organizan en forma jerárquica y cada nodo detecta deadlocks en los que estén involucrados sus descendientes.
23
Detección jerárquica de deadlock
Características:
Es el intermedio entre el centralizado y el distribuido.
Explota los patrones de comunicación locales a un grupo de nodos para detectar el deadlock.
No es dependiente de la falla de un nodo.
Un nodo no está sobrecargado por la detección de deadlock en los cuales muy posiblemente no está involucrado.
24
Resolución del deadlock
La persistencia de un abrazo mortal tiene dos efectos negativos sobre el rendimiento de un sistema:
Los recursos en manos de procesos interbloqueados no están disponibles a otros procesos.
El tiempo mientras persista el deadlock se suma al tiempo de respuesta de cada proceso interbloqueado.
25
Resolución del deadlock
La espera por recursos agrega arcos y nodos al grafo de asignación de recursos.
La resolución de deadlock remueve arcos y nodos del grafo de asignación de recursos.
26
Prevención distribuida de deadlock
Algoritmo Espera-Muere.
27
Prevención distribuida de deadlock
Algoritmo Herida-Espera.
28
 Página anterior | Volver al principio del trabajo | Página siguiente  |